from utils.log import Log
from utils.tree_node import TreeNode
from utils.raw_obj import RawObject as Obj
from utils.qs import QS
from algo.tree.tree_generator import TreeGenerator


class TreeSerialize(Log):
    def __init__(self):
        # ref: https://www.bilibili.com/video/BV1Rp4y1g7ys/?spm_id_from=333.999.0.0&vd_source=ad559e41b561d48861f70d0187e51e02
        # 01:06:12
        # *: 叶子节点
        # #: 非叶子节点
        super(TreeSerialize, self).__init__()

    @staticmethod
    def serialize(root):
        s = []
        # 不知道为什么,不加默认参数,val里面会有一些默认值,也不是generator的一些残留
        # 在generator.do()返回之前已经clean掉了queue里面的内容,也不行
        # 以后针对默认参数的,尽量都传参吧
        q = QS(is_queue=True, val=[])
        if root:
            q.push(root)
            s.append(root.val.val if isinstance(root.val, Obj) else root.val)
        while len(q):
            n = q.pop()
            if n.left is None and n.right is None:
                s.append('*')
            elif n.left is None:
                s.append('#')
                s.append(n.right.val.val if isinstance(n.right.val, Obj) else n.right.val)
                q.push(n.right)
            elif n.right is None:
                s.append(n.left.val.val if isinstance(n.left.val, Obj) else n.left.val)
                q.push(n.left)
                s.append('#')
            else:
                s.append(n.left.val.val if isinstance(n.left.val, Obj) else n.left.val)
                q.push(n.left)
                s.append(n.right.val.val if isinstance(n.right.val, Obj) else n.right.val)
                q.push(n.right)
        return ','.join([str(i) for i in s])

    @staticmethod
    def generate(s):
        return None if s == '#' else TreeNode(s)

    @staticmethod
    def deserialize(serialize_s):
        s = serialize_s.split(',')
        q = QS(is_queue=True, val=[])
        if not s:
            return None
        root = TreeNode(s.pop(0))
        q.push(root)
        while len(q):
            n = q.pop()
            left = s.pop(0)
            if left == '*':
                continue
            else:
                right = s.pop(0)
                n.left = TreeSerialize.generate(left)
                n.right = TreeSerialize.generate(right)
                if n.left:
                    q.push(n.left)
                if n.right:
                    q.push(n.right)
        return root


if __name__ == '__main__':
    g = TreeGenerator()
    s = TreeSerialize.serialize(g.do())
    print(s)
    print(TreeSerialize.serialize(TreeSerialize.deserialize(s)))
